• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    The present invention provides an IP address look-up method that can look up IP (Internet Protocol) addresses without having to sort the prefixes of the routing table in order of length or do a feedback search. The IP address look-up method of the present invention provides a method for comparing prefix lengths of mask strings corresponding to set match lines when at least one match line is set in a three-way CAM (Content Addressable Memory). And determining a routing entry corresponding to the mask string having the longest prefix length as a longest prefix matching (LPM) entry.
    公开号:KR20040003258A
    申请号:KR1020020037911
    申请日:2002-07-02
    公开日:2004-01-13
    发明作者:박영근；문강영；강병창；최병구
    申请人:삼성전자주식회사；연세대학교；
    IPC主号:
    专利说明:

    INTERNET PROTOCOL ADDRESS LOOK-UP METHOD}
    [9] The present invention relates to Internet Protocol (IP) addressing, and more particularly to a method of looking up an IP address using a ternary Content Addressable Memory (CAM).
    [10] Today, with the explosive growth of Internet users, the increase in the underlying network traffic, which requires broadband such as multimedia, has significantly degraded the quality of Internet services, and attempts to solve this have been widespread. It is done.
    [11] Three important design issues to consider in next-generation router designs for quality Internet services are link speed, switching speed, and packet throughput. Among them, the link speed and the switching speed are almost satisfactory since the development of optical technology enables transmission of router inputs and outputs at speeds of several tens of gigabytes. However, there are many problems with regard to packet throughput.
    [12] Especially when the router looks up the IP address, the characteristics of the IP address scheme face the problem of Longest Prefix Matching (LPM). The IP address look-up looks at the destination address contained in the header of the IP packet for forwarding the IP packet, looks up the entry of the corresponding address in the routing table, and next-hop. It means to figure out. The IP address is represented by a prefix of unspecified length, and the result of the routing search by look-up is the output link, i.e., the next path value, to the final destination of the IP packet. Routing lookup is performed based on the LPM method, which selects the entry with the longest prefix in the routing table. The LPM problem described above is an IP address called Classless Inter-Domain Routing (CIDR). This problem is caused by the widespread use of address allocation. CIDR was officially documented in 1993 as Request for Comments (RFC) 1517, 1518, 1519, and 1520, removing the concept of traditional Class A, Class B, and Class C networks in IP addresses. The CIDR reduces the class C address space and class A and B address space caused by IP address allocation, thus enabling efficient IP address allocation. However, the number of entries in the routing table that the router must maintain has increased significantly, resulting in slower IP address lookups.
    [13] The IP look-up technology currently proposed for the development of high-speed routers is based on hardware-based technologies using CAM (Content Addressable Memory), caching, and large-memory structures, and LC ( Level Compressed can be divided into software based technologies such as trie, hashing and multibit trie. The implementation of the IP address lookup by software has the advantage of being more flexible and easily adaptable to modification of the protocol. However, implementing IP look-ups by hardware requires high-speed packet processing that cannot be achieved by software. As a result, almost all high-speed routers of today's major router vendors perform IP address look-up by hardware.
    [14] Used to implement the IP look-up function by hardware, the CAM performs the exact match search operation in one clock cycle. The CAM compares the input search key in parallel with all entries in the CAM, i.e. all elements stored in segments that are physically partitioned within the CAM, and as a result the physical key storing the element matching the search key is stored. Print the address of the segment. If there is any data related to the matched element, this data is also output. As such, the CAM enables fast retrieval by comparing the search key in parallel with all entries in the CAM and outputting the results, typically having a very short latency time of 10-20 ms.
    [15] A ternary CAM, on the other hand, is a more flexible type of CAM that allows you to compare incoming search keys with storage elements of different lengths. In such a ternary CAM, there is a mask bit string that conforms to the content bit string so that not all of the content bit strings need to be compared with the search key. The three-way CAM also supports search speeds that are several times the rate typically required for OC-192 or 10 Gigabit Ethernet, and can handle up to 129K routes on a single chip. Accordingly, three-way CAM can be used to determine Longest Prefix Matching (LPM), and the speed of three-way CAM is suitable for packet forwarding.
    [16] A schematic structural diagram of the IP address look-up apparatus using the three-way CAM described above is shown in FIG. As shown in FIG. 1, the ternary CAM 100 stores a plurality of routing entries 102 each having a prefix, one in physically divided segments. These routing entries 102 are stored from the physically low address in order of their prefix length. These prefixes are compared in parallel with a search key, which is a destination address extracted from the header of the IP packet to be forwarded, and the comparison finds a routing entry with a prefix that matches the search key. As a result of this search, the ternary CAM 100 sets the match line of the routing entry with the prefix that matches the search key to " 1. " Here, "1" means logic "1" and is the same in the following description. Likewise, in the following description, "0" means logic "0". Priority encoder 104 is connected to the match lines of routing entries 102 of ternary CAM 100. Priority encoder 104, if there is at least one routing entry that matches the search key, i.e. the set match line, then the lowest address of the matched routing entries, i.e., the LPM with the longest prefix length. It will find and print the physical address of the entry. In this way, the physical address of the LPM entry output from the priority encoder 104 is applied to a memory (not shown) that stores the following path values, and one memory is output by outputting the next path value stored at this address. The IP address lookup for the IP packet is completed.
    [17] In the IP address look-up scheme of FIG. 1 as described above, since the prefixes are stored in length order, the lowest address among the match lines set by the search result is automatically LPM. However, to be stored in the prefix order is the biggest disadvantage of the method using the three-way CAM as shown in FIG. If a new prefix needs to be added when the routing table is updated, all prefixes shorter than the new prefix must be moved to a higher address and stored again in order to maintain the length order in the ternary cam 100. Updating the routing table by reordering the prefixes like this requires more time than the IP address look-up, and the IP address look-up is not necessary because the routing table must be kept off-line during the sorting process. Not done.
    [18] As a way of solving the disadvantages of updating the routing table, unused storage spaces are maintained between a set of prefixes of length i and i + 1. That is, routing entries are divided by prefix length, and free storage space remains in each prefix set to facilitate the addition of new routing entries. However, this empty storage space causes a waste of storage space of the three-way CAM. Also, when the empty storage space fills up, routing entries must be relocated, during which the routing table must be kept off-line, so no IP address look-up is done. Due to the recent introduction of mobile IP, frequent routing updates in routers are expected to increase IP address look-up idle time and drastically reduce IP address look-up performance.
    [19] On the other hand, the VLMP (Vertical Logical Operation with Mask Encoded Prefix Length) method proposed by NEC Kobayashi et al. Removes the constraint that prefixes should be stored in order of their length. The VLMP scheme is described by Kobayashi, M., Murase, T., and Kuriyama, A. in "A Longest Prefix Match Search Engine for Multi-Gigabit IP Processing", IEEE International Conference on Communications , vol. 3, June 2000, pp.1360-1364. A schematic structural diagram of the VLMP type IP address look-up apparatus disclosed in this document is shown in FIG. 2, and a block diagram showing a more detailed configuration is shown in FIG. 2 and 3 are respectively shown in the above document as FIGS. 1 (b) and 5, and FIG. 1 described above is shown in the above document as FIG. 1 (a).
    [20] Looking at the IP address look-up of the VLMP method with reference to the above-mentioned documents are as follows. First, as shown in FIG. 2, in the ternary CAM 200, a plurality of routing entries 202 each having a prefix are stored in physically divided segments, unlike in FIG. 1. Stored regardless of the order of prefix length. The ternary CAM 200 retrieves a matching prefix by parallel comparison with the search key and the prefixes of the routing entries 202 and outputs the prefix length information of the matching routing entry. When there is at least one matching routing entry as described above, the LPM should be selected from the matching routing entries as described above. To this end, in the VLMP circuit 204 which performs secondary search by performing a predetermined logical operation on the output of the ternary CAM 200 as shown in FIG. In operation 200, an LPM entry that satisfies the LPM among routing entries matched by the search is determined using length information of the matched prefixes. The physical address of the LPM entry thus determined is output by the encoder 206.
    [21] Referring now to FIG. 3, a number of routing entries 302 are connected to the output of the key register 300 that temporarily stores the search key, and an encoder 206 is connected to the output of the routing entries 302. Routing entries 302 have a pair of equal length strings, n bits of data string DS and mask string MS. The data string DS refers to a data bit string including a prefix of an IP address corresponding to each routing entry, starting with a Most Significant Bit (MSB), and the remaining bits are filled with "0". The mask string MS is a mask bit string representing the prefix length of the corresponding IP address, where each mask bit is filled with a contiguous " 1 " bit string equal to the length of the prefix from the MSB, with the remainder filled with " 0 ". For example, to represent the prefix "110", the data string is "11000000" and the mask string is "11100000".
    [22] In FIG. 3, the LPM search for the search key stored in the key register 300 is executed by two stages as follows.
    [23] First stage
    [24] 1-1. The search key K stored in the key register 300 is linked to the entries 302.
    [25] 1-2. At block 304 of each entry, a mask comparison, R1: = (K & MS) XNOR (DS & MS) is performed. Here, "&" means bitwise AND operation, and "XNOR" means bitwise exclusive NOR operation.
    [26] 1-3. In block 304 of each entry, all the bits of R1 are ANDed, and the result is provided to match line 1.
    [27] 1-4. If match line 1 is set to "1", selector S2 sends mask string MS to the VLMP line. Otherwise, selector S2 sends " 00 ... 0 " of the same length as mask string MS to the VLMP line.
    [28] 1-5. At each bit position of the VLMP line, a vertical bitwise logical OR operation, ie, VLMP, is performed. This result is represented by RV in FIG. 3.
    [29] Second stage
    [30] 2-1. RV is connected to entries 302.
    [31] 2-2. In block 306 of each entry, the two bit strings, RV and mask string MS, are compared exactly. That is, R2: = RV NOR MS is performed.
    [32] 2-3. In block 306 of each entry, all the bits of R2 are ANDed, and the result is provided to match line 2.
    [33] 2-4. If match line 1 and match line 2 of any entry are both "1", selector S1 sends a "1" to the LPM line. Otherwise, selector S1 sends " 0 " to the LPM line.
    [34] According to the two stages as described above, only the LPM line of the routing entry determined as the LPM entry among the routing entries 302 is set to "1". Accordingly, the encoder 206 connected to the LPM lines of the routing entries 302 finds and outputs the physical address of the routing entry corresponding to the LPM line set to "1".
    [35] For example, four prefixes P1 = "110", P2 = "1001", P3 = "11011", and P4 = "1101" are stored one after the other in the routing entries 302 in order from the first routing entry to the fourth routing entry. Assuming that the search key was entered as "11011111" in the presence of a state, the prefixes of the first, third, and fourth routing entries will be matched first in parallel with the prefixes. The VLMP is then performed on the mask strings corresponding to the prefix of the first, third and fourth routing entries. In the above example, the mask string P1_mask = "11000000", P3_mask = "11111000", P4_mask = "11110000", and the VLMP result is "11111000". These VLMP results are the same regardless of the storage order of the mask strings. As a result, the prefixes do not have to be in length order. Once the result of the VLMP is obtained, it can be seen that the LPM has occurred for the entry containing the mask string that fully matches the result of the VLMP. Subsequently, when the result of VLMP is compared with P1_mask, P3_mask, and P4_mask in the second "11111000", it can be seen that this entry becomes an LPM entry because the third entry is matched.
    [36] As described above, according to the VLMP IP address look-up, the LPM entry can be found even if the prefixes are not arranged in length order. As a result, even if a new prefix is to be added when the routing table is updated, the prefixes do not need to be rearranged, so the update is performed quickly. However, VLMP must be added and the VLMP result fed back as a search key, with additional circuitry added. Therefore, the VLMP IP address look-up device is manufactured with a dedicated Large Scale Integration (LSI) that includes these additional circuits.
    [37] As described above, the IP address look-up schemes proposed so far have a disadvantage in that the prefixes of the routing table must be sorted in order of length, or a circuit for feedback searching must be added to the ternary CAM even if they are not ordered.
    [38] Accordingly, an object of the present invention is to provide an IP address look-up method capable of looking up an IP address without the necessity of sorting the prefixes of the routing table in order of length or performing a feedback search.
    [39] Another object of the present invention is to provide an IP address look-up method capable of quickly updating a routing table while also looking up an IP address using a universal three-way CAM.
    [1] 1 is a schematic structural diagram of an IP address look-up apparatus using three-way CAM;
    [2] 2 is a schematic structural diagram of a VLMP type IP address look-up device;
    [3] 3 is a block diagram of a VLMP type IP address look-up device;
    [4] 4 is a schematic structural diagram of an IP address look-up apparatus using ternary CAM according to an embodiment of the present invention;
    [5] 5 is a block diagram of an IP address look-up apparatus using three-way CAM according to an embodiment of the present invention;
    [6] 6 is a process flow diagram of a priority encoder according to an embodiment of the present invention;
    [7] 7A to 7D illustrate an LPM search operation of a priority encoder according to an embodiment of the present invention.
    [8] 8 is an exemplary view illustrating a simulation result of an IP address look-up apparatus using three-way CAM according to an embodiment of the present invention.
    [40] The method of the present invention for achieving the above object, the process of comparing the prefix length of the mask strings that are output corresponding to the set match line when at least one match line is set in the three-way CAM, and the prefix length is And determining a routing entry corresponding to the longest mask string as a longest prefix matching (LPM) entry.
    [41] Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. In the following description, detailed descriptions of well-known functions and configurations that may unnecessarily obscure the subject matter of the present invention will be omitted.
    [42] 4 is a schematic structural diagram of an IP address look-up apparatus using ternary CAM according to an embodiment of the present invention. The IP address look-up apparatus of the present invention comprises a conventional three-way CAM 400 and a priority encoder 404 connected to the output of the three-way CAM 400. In the ternary CAM 400, a plurality of routing entries 402, each having a prefix, are stored in physically divided segments, as shown in FIG. 4, regardless of the order of the prefix lengths. The ternary CAM 400 retrieves the matching prefix by parallel comparison with the search key and the prefixes of the routing entries 402, sets the match line of the matching routing entry, and also sets the mask string of the matching routing entry. Is output to the priority encoder 404. The priority encoder 404 then corresponds to the match lines set when at least one or more match lines are set in the ternary CAM 400, ie, when one or more of the match lines of the routing entries 402 are set. The routing length corresponding to the longest mask string is determined as the LPM entry by comparing the prefix lengths of the mask strings, and the physical address of the LPM entry is output based on the match line of the LPM entry.
    [43] Referring to the block diagram of Fig. 5 showing the IP address look-up apparatus according to the embodiment of the present invention as described above, the ternary CAM 400 is output to the output of the key register 500 to temporarily store the search key. A number of routing entries 402 are connected, and a priority encoder 404 is connected to the output of routing entries 402 of this ternary CAM 400. The routing entries 402, like the routing entries 302 of FIG. 3 described above, have a pair of bit strings of equal length, i.e., n-bit data string DS and mask string MS. The search key of the key register 500 is connected to the routing entries 402, and in block 502 of each routing entry, R1: = (K & MS) XNOR (as in block 304 of FIG. DS & MS) is performed. And at block 502 of each entry, all the bits of R1 are ANDed, and the result is provided to the match line. In each entry, the selector 506 that selects " 00 ... 0 " or mask string MS consecutively the same length as the mask string MS and outputs to the priority encoder 404 according to whether the match line is set or not, If set to "1", it exports the mask string MS, otherwise it exports "0 ... 0".
    [44] As described above, when at least one match line is set in the ternary CAM 400, the priority encoder 404 compares the prefix lengths of the mask strings output from the ternary CAM 400 corresponding to the set match line. To determine the routing entry corresponding to the longest mask string as the LPM entry. The priority encoder 404 then outputs the determined physical address of the LPM entry based on the match line of the LPM entry as in FIG. 1. At this time, the priority encoder 404 compares the lengths of the mask strings starting from the Most Significant Bit (MSB) to determine the LPM entry. This comparison from the MSB is because, as described above, the mask string is filled with consecutive "1" bit strings equal to the length of the prefix from the MSB, and the rest are all filled with "0".
    [45] As described above, a process flow diagram in which the priority encoder 404 compares the lengths of the mask strings to determine the LPM entry and outputs its physical address is shown in steps 600 to 610 of FIG. 7A to 7D are shown, for example, when there are three mask strings to compare the search operation example. If at least one or more match lines are set in the ternary CAM 400, the priority encoder 404 outputs the MSB and LSB as shown in FIG. 7A for the mask strings corresponding to the match lines set in step (600). Specify upper and lower pointers respectively. In operation 602, a check pointer is designated at an intermediate position between the upper pointer and the lower pointer as shown in FIG. 7B. Next, in step 604, it is checked whether the number of bits indicating that the bit value indicated by the check pointer is a prefix, that is, the number of bits having a value of "1" is one. If there are two or more bits of "1", the lower pointer is moved to the position of the check pointer as shown in FIG. 7C in step 606, and the process is repeated again from step 602. As a result of reprocessing steps 602 to 604, if there are two or more bits that are still " 1 ", in step 606, the lower pointer is moved to the position of the check pointer as shown in FIG. Process again from the step. In this way, when the number of bits of "1" becomes one as shown in FIG. 7D, in step 608, the routing entry corresponding to the mask string of which the bit value indicated by the check pointer at that time is "1" is determined as the LPM entry. Thereafter, the physical address of the LPM entry thus determined in step 610 is output based on the match line of the LPM entry as in FIG. 1.
    [46] Therefore, in the present invention, like the VLMP method, even if the prefixes are stored in the three-way CAM regardless of the length order, unlike the VLMP method, no feedback search is required. As a result, the routing table can be updated quickly, but only the priority encoder needs to be changed. Thus, unlike the VLMP method, the IP address can be looked up using a general purpose three-way CAM instead of a dedicated LSI.
    [47] For reference, as a result of performing the simulation by writing the priority encoder 404 as described above in VHDL (Very high speed Hardware Description Language) code, as shown in FIG. It took about 시간 time. FIG. 8 shows that when the prefix length is 27 bits, the second mask string MS1 of the five mask strings MS0 to MS4 is determined to correspond to the LPM entry, so that the physical address ADDRESS of the second routing entry is output as “00010”. In addition to the above 40 ms, if the parallel search is performed in the three-way CAM and the result is 10 ms, the total time is 50 ms. This enables about 25 million searches per second. Therefore, it can be applied to IP backbone routers with 10Gbps input / output and requiring 1000 router table updates per second, as well as OC-192 per port that can be used in the currently developed terabit router. It can support forwarding speed of 9.6Gbps.
    [48] Meanwhile, in the above description of the present invention, specific embodiments have been described, but various modifications can be made without departing from the scope of the present invention. Particularly, in the embodiment of the present invention, the LPM entry is found by comparing the lengths of the mask strings while moving the lower pointer to the position of the check pointer. However, the lengths of the mask strings may also be compared and searched. Therefore, the scope of the invention should not be defined by the described embodiments, but should be defined by the equivalent of claims and claims.
    [49] As described above, the present invention uses a universal three-way CAM while allowing prefixes to be updated quickly, because the prefixes are stored in the three-way CAM regardless of the length order, and unlike the VLMP method, the feedback search is not required. This has the advantage of looking up IP addresses.
    权利要求:
    Claims (2)
    [1" claim-type="Currently amended] Routing entries each including a pair of data strings containing a prefix of an Internet Protocol (IP) address and a mask string indicating a length of the prefix, and a search key and a routing key which are destination addresses of IP packets to be forwarded. A method of looking up an IP address of an IP packet to be forwarded by using a three-way Content Addressable Memory (CAM) that sets a match line of a matching routing entry to compare and outputs a mask string thereof,
    Comparing prefix lengths of mask strings corresponding to the set match lines when at least one match line is set in the three-way CAM;
    And determining a routing entry corresponding to the mask string having the longest prefix length as a longest prefix matching (LPM) entry.
    [2" claim-type="Currently amended] Routing entries each including a pair of data strings containing a prefix of an Internet Protocol (IP) address and a mask string indicating a length of the prefix, and a search key and a routing key which are destination addresses of IP packets to be forwarded. A method of looking up an IP address of an IP packet to be forwarded by using a three-way Content Addressable Memory (CAM) that sets a match line of a matching routing entry to compare and outputs a mask string thereof,
    Assigning an upper pointer and a lower pointer to the MSB and the LSB for mask strings output corresponding to the set match lines when at least one match line is set in the three-way CAM;
    Assigning a check pointer to a bit at an intermediate position between the upper pointer and the lower pointer;
    Checking the number of bits indicating that a bit value indicated by the check pointer in the mask strings is a prefix bit;
    If the number of bits indicating the prefix is one, the routing entry corresponding to the mask string, which is a value indicating that the bit value indicated by the check pointer is the prefix bit, is determined as a Longest Prefix Matching (LPM) entry. And moving to the location of the check pointer and specifying the check pointer, and then proceeding to the check pointer designation process.
    类似技术:
    公开号 | 公开日 | 专利标题
    US9627063B2|2017-04-18|Ternary content addressable memory utilizing common masks and hash lookups
    JP5525272B2|2014-06-18|System for forwarding packets with hierarchically structured variable length identifiers using an exact match search engine
    Eatherton et al.2004|Tree bitmap: hardware/software IP lookups with incremental updates
    Gupta et al.1998|Routing lookups in hardware at memory access speeds
    Basu et al.2005|Fast incremental updates for pipelined forwarding engines
    US8401013B2|2013-03-19|Congestion management in a network
    JP5525273B2|2014-06-18|System for forwarding packets with hierarchically structured variable length identifiers
    US7633960B2|2009-12-15|Dense mode coding scheme
    US7913060B2|2011-03-22|Method and apparatus for physical width expansion of a longest prefix match lookup table
    US7738454B1|2010-06-15|Methods and apparatus related to packet classification based on range values
    US5946679A|1999-08-31|System and method for locating a route in a route table using hashing and compressed radix tree searching
    CA2363963C|2007-04-24|Network router search engine using compressed tree forwarding table
    US6067574A|2000-05-23|High speed routing using compressed tree process
    US6957272B2|2005-10-18|Stackable lookup engines
    US7536476B1|2009-05-19|Method for performing tree based ACL lookups
    US7058642B2|2006-06-06|Method and data structure for a low memory overhead database
    US7017021B2|2006-03-21|High-speed message forwarding lookups for arbitrary length strings using pipelined memories
    US7116663B2|2006-10-03|Multi-field classification using enhanced masked matching
    US7236492B2|2007-06-26|Configurable packet processor
    JP4452183B2|2010-04-21|How to create a programmable state machine data structure to parse the input word chain, how to use the programmable state machine data structure to find the resulting value corresponding to the input word chain, deep wire speed A method for performing packet processing, a device for deep packet processing, a chip embedding device, and a computer program including programming code instructions |
    US7634500B1|2009-12-15|Multiple string searching using content addressable memory
    EP1535430B1|2007-10-03|Method for routing of data packets and routing apparatus
    US8625604B2|2014-01-07|Hash-based prefix-compressed trie for IP route lookup
    US6691218B2|2004-02-10|Method and apparatus for longest match address lookup
    US6243720B1|2001-06-05|Address translation method and system having a forwarding table data structure
    同族专利:
    公开号 | 公开日
    KR100460188B1|2004-12-08|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    2002-07-02|Application filed by 삼성전자주식회사, 연세대학교
    2002-07-02|Priority to KR10-2002-0037911A
    2003-06-17|Priority claimed from US10/462,778
    2004-01-13|Publication of KR20040003258A
    2004-12-08|Application granted
    2004-12-08|Publication of KR100460188B1
    优先权:
    申请号 | 申请日 | 专利标题
    KR10-2002-0037911A|KR100460188B1|2002-07-02|2002-07-02|Internet protocol address look-up method|
    [返回顶部]